0740. 删除并获得点数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i]，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

---

示例 1：

输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

---

提示：

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 10^4

2. 🎯 s.1 - 动态规划

c

int deleteAndEarn(int* nums, int numsSize) {
    int mx = 0;
    for (int i = 0; i < numsSize; i++) if (nums[i] > mx) mx = nums[i];
    int* sum = (int*)calloc(mx + 1, sizeof(int));
    for (int i = 0; i < numsSize; i++) sum[nums[i]] += nums[i];
    int prev = 0, curr = sum[0];
    for (int i = 1; i <= mx; i++) {
        int tmp = curr;
        curr = curr > prev + sum[i] ? curr : prev + sum[i];
        prev = tmp;
    }
    free(sum);
    return curr;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function (nums) {
  const max = Math.max(...nums)
  const sum = new Array(max + 1).fill(0)
  for (const n of nums) sum[n] += n
  let prev = 0,
    curr = sum[0]
  for (let i = 1; i <= max; i++) {
    const tmp = curr
    curr = Math.max(curr, prev + sum[i])
    prev = tmp
  }
  return curr
}

py

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        mx = max(nums)
        total = [0] * (mx + 1)
        for n in nums:
            total[n] += n
        prev, curr = 0, total[0]
        for i in range(1, mx + 1):
            prev, curr = curr, max(curr, prev + total[i])
        return curr

• 时间复杂度：$O(n+m)$，其中 n 是数组长度，m 是最大值
• 空间复杂度：$O(m)$

算法思路：

• 转化为“打家劫舍”问题：先统计每个值的总和
• dp[i] = max(dp[i-1], dp[i-2] + sum[i])，选了 i 就不能选 i±1
• 用滚动变量优化空间